# 二叉树展开为链表

# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution(object):
    def flatten(self, root):
        """
        :type root: TreeNode
        :rtype: None Do not return anything, modify root in-place instead.
        """
        pre = list()

        def preOrder(root):
            if not root:
                return
            pre.append(root.val)
            preOrder(root.left)
            preOrder(root.right)
        preOrder(root)

        for i in pre[1:]:
            node = TreeNode(i)
            root.right = node
            root.left = None
            root = root.right


class Solution(object):
    def flatten(self, root):
        """
        :type root: TreeNode
        :rtype: None Do not return anything, modify root in-place instead.
        """
        current = root
        while current:
            if current.left:
                pre = index = current.left
                while pre.right:
                    pre = pre.right # 找到左子树的最右边的结点
                pre.right = current.right # 作为右子树的前驱
                current.left = None
                current.right = index
            current = current.right